home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9501 / E_HAZAS.CD < prev    next >
Text File  |  1995-10-27  |  7KB  |  111 lines
  1.       @VRejtvénymegfejtés@N
  2.  
  3.       @VPárkeresés magyar módra@N
  4.  
  5.           Senki  ne  gondoljon itt  semmiféle  rosszra, magazinunk
  6.       mûfajától  idegen   dologra,  csupán   (sajnos?)  augusztusi
  7.       feladványunk megoldásáról lesz szó a továbbiakban.
  8.           Bonifert Csaba javasolta a következô feladat  kitûzését:
  9.       egy   társkeresô   irodában   minden   fiúról   és   lányról
  10.       nyilvántartják, hogy kölcsönösen szimpatizálnak-e egymással.
  11.       Feladat a fiúkat és  lányokat úgy párosítani, hogy  a lehetô
  12.       legkevesebben   maradjanak   pár   nélkül   (csak   fiú-lány
  13.       kapcsolatok  lehetségesek,  s  azok  is  monogám   jellegûek
  14.       legyenek!).
  15.           ùgy tûnik,  kezd kiegyenlítôdni  a nem  hivatalos nyelvi
  16.       versengés eredménye: négy megfejtônk közül ketten C,  ketten
  17.       Pascal  nyelvû programot  küldtek, a  mégis megmaradó  enyhe
  18.       Pascal   fölényt   (3:2)  Déri   Attila   kétféle  megoldása
  19.       biztosítja.
  20.           Ismét   (sokadszor)   gráfelméleti   probléma   szerepel
  21.       rovatunkban, talán nem véletlenül. A gráfok rendkívül sok --
  22.       egymástól  igen  eltérô  módon  megfogalmazható  -- probléma
  23.       leírására alkalmazhatók, közlekedési, szállítási kérdésektôl
  24.       kezdve áramkörtervezési feladatokon keresztül sportversenyek
  25.       lebonyolításának megszervezéséig, vagy -- mint látható --  a
  26.       házasságközvetítésig.
  27.           Hogyan tudnánk tehát a kitûzött problémát pontosabban --
  28.       némi gráfelméleti terminus  technicust használva --  leírni?
  29.       ùgynevezett  páros  gráffal van  dolgunk,  mert pontjai  két
  30.       olyan csoportra oszthatók  (tudniillik fiúkra és  lányokra),
  31.       melyeken belül nincs él (kapcsolat), tehát él csak különbözô
  32.       halmazba  tartozó   pontokat  köthet   össze.  Ráadásul   mi
  33.       független éleket -- azaz olyanokat, melyeknek nincsen  közös
  34.       pontjuk -- keresünk, ezzel zárva ki a  többnejû(férjû)séget.
  35.       Ennek alapján a feladat  egy páros gráf maximális  független
  36.       élhalmazának  megkeresését   jelenti,  tehát   a  párosítási
  37.       probléma egy speciális esetével van dolgunk.
  38.           Két út áll elôttünk: megpróbálhatjuk gráfunkat  teljesen
  39.       általánosan, szisztematikusan feldolgozni, azaz  elôállítjuk
  40.       az  adott  pontok  és  élek  alapján  az  összes  lehetséges
  41.       kombinációt, s kiválasztjuk a maximális élszámút.  Sejthetô,
  42.       hogy a méretek növekedtével ez a metódus igencsak  lelassul,
  43.       hiszen  drámai  mennyiségû  lesz  a  lehetséges  kombinációk
  44.       száma. Kellene  tehát egy  hatékonyabb eljárás.  Ez lesz  az
  45.       úgynevezett ""magyar módszer", amely Kônig Dénes és Egerváry
  46.       Jenô nevéhez  fûzôdik (a  század elsô  felébôl), s  amelynek
  47.       leírása  megtalálható  például Andrásfai  Béla  Ismerkedés a
  48.       gráfelmélettel, vagy Lovász-Gács szerzôpáros Algoritmusok c.
  49.       könyveiben.  Ezt  a  módszert  (is)  ""programozta  be" Déri
  50.       Attila, és Tóth Zoltán.
  51.           Mi is tehát ez a magyar módszer (másképpen az  alternáló
  52.       utak módszere)? Képzeljük el  (páros) gráfunkat úgy, hogy  a
  53.       két halmaz  pontjait (a  fiúkat, illetve  a lányokat)  alul,
  54.       illetve fölül egy egyenes mentén rajzoljuk fel, a  szimpátia
  55.       kapcsolatokkal egyetemben.  Kezdjünk kiválasztani  független
  56.       éleket  (mondjuk  vastagítsuk  meg  a  választott  vonalat).
  57.       Elôbb-utóbb megakadunk,  pedig még  maradt pártában  leányzó
  58.       vagy legény. S most jön az algoritmus lényege: olyan  utakat
  59.       (összefüggô élsorozatokat) fogunk  keresni, amelyek fel  nem
  60.       használt  alsó pontokon  indulnak, minden  második élük  már
  61.       vastag, és  felsô, fel  nem használt  ponton végzôdnek.  Egy
  62.       ilyen  út  ""vastag"  éleit  az  út  többi  élére kicserélve
  63.       (azokat megvastagítva),  a független  élek számát  növeljük.
  64.       (Érdemes egy kis ábrát rajzolva kipróbálni az eljárást.)
  65.           Most már csak az a kérdés, hogyan tudjuk  ""lefordítani"
  66.       ezt  (Tóth  Zoltán kifejezését  kölcsönvéve)  a ""szeret-nem
  67.       szeret" mátrix feldolgozására, hiszen ez, a csupa nullát  és
  68.       egyest  tartalmazó  tömb  (""hivatalosan"  adjacencia-mátrix
  69.       vagy szomszédossági mátrix) adja a kapcsolatok és így a gráf
  70.       legkézenfekvôbb  gépi  ábrázolását  (olvasóink  is  ezt   az
  71.       ábrázolásmódot  választották).  Világos, hogy  az  éleknek a
  72.       tömbbéli egyesek felelnek  meg, így a  fenti vonalvastagítás
  73.       valamely 1-es  megjelölését (pl.  értéke megnövelését  2-re)
  74.       jelenti. Jelöljük (jegyezzük) meg az összes olyan  oszlopot,
  75.       amelybôl nem választottunk 1-est, majd a sorokra térünk  át:
  76.       azokat  jelöljük meg,  amelyek a  jelölt oszlopokat  1-esben
  77.       metszik, végül visszatérve az oszlopokra megjelöljük azokat,
  78.       amelyek a jelölt sorok  valamelyikét 2-esben metszi. Ha  már
  79.       nem tudunk ezen szabályok szerint jelölni (mondjuk áthúzni),
  80.       akkor  vizsgáljuk  meg   azon  megjelölt  sorokat,   amelyek
  81.       legfeljebb 1-est tartalmaznak. Megkeressük azt az 1-est, ami
  82.       miatt ezt a sort áthúztuk, ennek oszlopában azt a 2-est, ami
  83.       az oszlop kihúzásának volt az oka... és így tovább. Eljutunk
  84.       egy olyan 1-eshez, amelynek oszlopában nincs 2-es: és  ekkor
  85.       ennek az útnak  az 1-eseit 2-re,  2-seit 1-re változtatva  a
  86.       kettesek  számát   növeltük.  (Ezt   a  gondolatmenetet   is
  87.       valószínûleg  könnyebb  papíron,  ceruzával,  egy barátságos
  88.       tömb mellett követni).
  89.           A fenti algoritmus rejtett módon két fontos gráfelméleti
  90.       tételt  is  tartalmaz.  König  Dénes  tétele  kimondja, hogy
  91.       bármely páros gráf független éleinek maximális száma egyenlô
  92.       az éleket leszúró pontok minimális számával -- ez egy  újabb
  93.       megoldási lehetôséget is jelenthet a feladatra. Hall  tétele
  94.       a probléma teljes  megoldhatóságára ad feltételt:  egy páros
  95.       gráfban akkor és csak akkor lehet minden ""alsó" ponthoz egy
  96.       vele  összekötött  ""felsô"  pontot  rendelni  (különbözôhöz
  97.       különbözôt, azaz független élt),  ha bármely @KN@N-re bármely  @KN@N
  98.       darab  alsó  pont  összesen  legalább  @KN@N  felsô  ponttal van
  99.       összekötve.  Ez utóbbi  tétel egy  játékosabb (és  könnyebb)
  100.       változata: egy  táncmulatságon @KK@N  férfi és  @KK@N nô  van jelen.
  101.       Mindenki  ismeri az  ellenkezô nemûeknek  legalább a  felét.
  102.       Bizonyítsuk be, hogy  valamennyien táncra perdülhetnek  úgy,
  103.       hogy ismerôssel ""lejtenek".
  104.           A havi nyertes  -- sorsolás eredményeképpen  -- Verbôczi
  105.       Zoltán lett, nyereménye  10 darab floppy.  A CT BBS-en  Tóth
  106.       Zoltán  gyöngyösi  megfejtônk  számos  extrával  ellátott  C
  107.       nyelvû  programját,  illetve az  ötletgazda,  Bonifert Csaba
  108.       (szintén C) megoldását találják meg olvasóink.
  109.  
  110.       @KBánhegyesi Zoltán@N
  111.